package com.xxd.algo.newcode.mid01.class04;

public class Code05_LCSubsequence {

    public static String lcse(String str1, String str2) {
        if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
            return "";
        }
        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        int[][] dp = getdp(chs1, chs2);
        int m = chs1.length - 1;
        int n = chs2.length - 1;
        char[] res = new char[dp[m][n]];
        int index = res.length - 1;
        while (index >= 0) {
            if (n > 0 && dp[m][n] == dp[m][n - 1]) {
                // 和左边的一列相等，说明 肯定不是以 m n 结尾，且是以 m n -1 结尾
                n--;
            } else if (m > 0 && dp[m][n] == dp[m - 1][n]) {
                // 和上面的一行相同，那说明肯定也不是以m n 结尾 m - 1 n 结尾
                m--;
            } else {
                // 说明肯定是以 m - 1 n - 1 结尾的
                res[index--] = chs1[m];
                m--;
                n--;
            }
        }
        return String.valueOf(res);
    }

    private static int[][] getdp(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < str2.length; i++) {
            if (dp[0][i - 1] == 1) {
                dp[0][i] = 1;
            } else {
                dp[0][i] = str1[0] == str2[i] ? 1 : 0;
            }
        }

        for (int j = 1; j < str1.length; j++) {
            if (dp[j - 1][0] == 1) {
                dp[j][0] = 1;
            } else {
                dp[j][0] = str1[j] == str2[0] ? 1 : 0;
            }
        }

        for (int row = 1; row < str1.length; row++) {
            for (int col = 1; col < str2.length; col++) {
                // 先判断不以 i j 同时结尾什么情况
                dp[row][col] = Math.max(dp[row - 1][col], dp[row][col - 1]);
                if (str1[row] == str2[col]) {
                    dp[row][col] = Math.max(dp[row][col], dp[row - 1][col - 1] + 1);
                }
            }
        }

        return dp;
    }

    /**
     * 暴力递归
     *
     * @param str1
     * @param str2
     * @return
     */
    private static int recursion(String str1, String str2) {
        if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
            return 0;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        return getMaxLength(chars1, chars2,
                chars1.length - 1, chars2.length - 1);
    }

    /**
     * 从左往右的尝试模型
     *
     * @param str1
     * @param str2
     * @param index1
     * @param index2
     * @return
     */
    private static int getMaxLength(char[] str1, char[] str2, int index1, int index2) {
        if (index1 == 0 && index2 == 0) {
            return str1[0] == str2[0] ? 1 : 0;
        }

        if (index1 == 0) {
            return str1[0] == str2[index2] ? 1 : getMaxLength(str1, str2, 0, index2 - 1);
        }

        if (index2 == 0) {
            return str1[index1] == str2[0] ? 1 : getMaxLength(str1, str2, index1 - 1, 0);
        }

        int res = 0;
        res = Math.max(
                getMaxLength(str1, str2, index1 - 1, index2),
                getMaxLength(str1, str2, index1, index2 - 1));

        if (str1[index1] == str2[index2]) {
            res = Math.max(getMaxLength(str1, str2, --index1, --index2) + 1, res);
        }

        return res;
    }


    public static void main(String[] args) {
        String str1 = "A1BC2D3EFGH45I6JK7LMN";
        String str2 = "12OPQ3RST4U5V6W7XYZ";

       /*
        String str1 = "12342225";
        String str2 = "1234xyz5";
        */
        //  System.out.println(recursion(str1, str2));
        System.out.println(lcse(str1, str2));
     //   System.out.println(recursion(str1, str2));

        // 求长度
        int[][] dp = getdp(str1.toCharArray(), str2.toCharArray());
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
    }
}